1. Field of the Invention
The present invention relates generally to an apparatus for implementing error-correct decoding in a digital data communications system, and more specifically to such an apparatus wherein a data frame is effectively error-correct decoded using estimated correlation between the data frame under error-correct decoding and one or more than one preceding data frames.
2. Description of Related Art
In order to correct channel bit errors induced during digital data transmission, it is well known in the art to add redundant bits to each binary code word (or data frame) to be transmitted. The code is thus provided with the capability of combating the channel noises.
Error correct (or control) coding for achieving reliable communications over a noisy transmission channel has been discussed in a variety of books. One example thereof is a book entitled "Essentials of Error-control coding Techniques" edited by Hideki IMAI and published 1990 by Academic Press, Inc., San Diego, Calif. 92101, U.S.A. (Prior Reference 1).
Before turning to the present invention it is deemed advantageous to discuss conventional error correct coding with reference to FIGS. 1-4.
FIG. 1 is a block diagram showing a simplified model of a typical digital data communications system (generally depicted by 10) to which the present invention is applicable. The system 10 includes a transmitter 12 and a receiver 14 interconnected via a transmission channel 16.
The transmitter 12 is provided with a message source 18 which can be either a person or a machine (e.g., a digital computer). A source output (depicted by S1), which is to be transmitted to the destination, can be either a continuous (analog) waveform or a sequence of discrete symbols. A source encoder 20 transforms the source output S1 into a sequence of binary digits (bits) denoted by S2.
It is assumed that the message source 18 takes the form of a continuous (analog) source. In such a case, the source encoder 20 involves analog-to-digital conversion. That is, the source output S1 is digitized at a predetermined time interval, and the digitized signal is encoded and usually compressed. Thereafter, the encoded signal (viz., S2) is applied to a convolutional encoder 22. Although not shown in FIG. 1, the output of the encoder 22 (depicted by C) is subject to suitable modulation and then transmitted to the receiver 14 via the transmission channel 16.
As shown in FIG. 1, the receiver 14 includes a maximum-likelihood decoder (viz., Viterbi decoder) 24 and a source decoder 26 from which an estimated message is derived.
Reference is made to FIG. 2 wherein a simplified example of the convolutional encoder 22 is shown in block diagram form.
The encoder 22 includes three delay lines or shift registers (denoted by D.sub.n, D.sub.n-1 and D.sub.n-2), two modulo-2 adders 40a-40b, and a parallel/serial (P/S) converter 42. Thus, the constraint length (K) of the encoder 22 is 3 (three) while the code rate (R) thereof is 1/2. The arrangement illustrated in FIG. 2 is well known in the art.
FIG. 3 is a state diagram of the encoder 22. In this figure, two consecutive bits within each oval indicates the bits held in the last two delay lines D.sub.n-2 and D.sub.n-1 of FIG. 2, and indicates an encoder state. The encoder states (00), (01), (10) and (11) are connected or looped by solid and broken line arrows. When a bit "1" is applied to the encoder 22, the encoder state is shifted to the other state or returned to the same state via a solid line arrow. On the other hand, when a bit "0" is applied to the encoder 22 then the encoder state is shifted to the other state or returned to the same state via a broken line arrow. The outputs of the convolutional encoder 22, issued in response to each bit applied thereto, are indicated as "00", "01", "10" and "11" beside the corresponding arrows.
The encoder 22 is initially set to the state (00) before a fresh bit sequence is applied. Therefore, when a first bit of the sequence is "0", the encoder state (00) remains unchanged. In this case, the output of the encoder 22 is "00". Following this, if the second bit is "1", the encode 26 takes the state (01) and issues two bits sequence "11". Thereafter, similar operations continues.
It is assumed that the bit sequence S2 applied to the convolutional encoder 22 is EQU S2=(0 1 0 0 1 . . . ) (1)
Thus, the bit sequence C, issued from the encoder 22 and transmitted over the channel 16, is given by EQU C=(00 11 01 11 11 . . . ) (2)
The bit sequence C is applied to the receiver 14 as a bit sequence CC (FIG. 1). It is assumed that the bit sequence C has been deteriorated during transmission such that the bit sequence CC is given by EQU CC=(01 10 01 01 11 . . . ) (3)
For a better understanding of the convolutional encoding and the Viterbi algorithm (under which the decoder 24 operates), it is convenient to rewrite the state diagram of FIG. 3 as a function of time. As is well known in the art, the resulting structure is called a trellis diagram and is illustrated in FIGS. 4-6.
The operation of the convolutional encoder 22 is again described using the trellis diagram of FIG. 4. As in the above, it is assumed that the bit sequence S2 (=0 1 0 0 1 . . . ) is applied to the encoder 22. The encoder 22 has been set to the state (00) prior to the bit sequence S2 being initially applied thereto. As mentioned above, when a bit "1" is applied to the encoder 22 at a given time point, the encoder 22 assumes a new state pointed by a solid line arrow at the next time point. On the other hand, when a bit "0" is applied to the encoder 22 at a given time point, the encoder 22 assumes a new state pointed by a broken line arrow at the next time point. Accordingly, the convolutional encoder 22 generates the output C (=00 11 01 11 11 . . . ) as highlighted by bold solid and broken line arrows in FIG. 4.
Each of FIGS. 5 and 6 shows a trellis diagram for discussing the operation of the maximum-likelihood (viz., Viterbi) decoder 24 of FIG. 1.
Each of FIGS. 5 and 6 indicates, at the upper portion thereof, the above mentioned bit sequences S2, C and CC. In FIGS. 5 and 6, each of the numerals above the decoder states enclosed by ellipses is a "decimal number" indicating a path metric. There are two branches or paths leaving and entering each decoder state. At each time unit (t=1, 2, 3, . . . ), one of the two paths entering each decoder state is selected by comparing two path metrics associated with the two paths in question as will be better understood as the description proceeds.
The maximum-likelihood decoder 24 is initialized such that the path metric of the decoder state (00) is 0 (decimal number) while each of the remaining path metrics of the other decoder states (01), (10) and (11) is a sufficiently large number such as 10 (decimal number). These path metrics in decimal numbers are shown in FIG. 5 at t=0.
In FIG. 5, the branch metric (viz., the Hamming distance in this case) between the states (00).sub.t=0 and (00).sub.t=1 is 1 (one). Similarly, the branch metric between the states (10).sub.t=0 and (00).sub.t=1 is 1 (one). However, the path metric of the state (00).sub.t=1 from the state (00).sub.t=1 is 1 (=0+1) (decimal number) while the path metric of the state (00).sub.t=1 from the state (10).sub.t=0 is 11 (0+10) (decimal number). Accordingly, the path leaving the state (00).sub.t=0 and entering the state (00).sub.t=1 is selected as a survivor path wherein the path metric is 1. In the similar manner, the survivor paths and the corresponding path metrics of the other states (01), (10), and (11) at t=1 are determined as shown in FIG. 5. The survivor paths until t=1 are highlighted (viz., denoted by bold solid and broken line arrows). The resulting path metrics at t=1 are shown above each decoder state.
FIG. 6 shows the survivor paths from t=0 to t=5, which are highlighted in the figure, together with the path metrics thereof. As shown in FIG. 6, each of the path metrics of the decoder states (10).sub.t=5 and (11).sub.t=5 exhibits the smallest one. It is to be noted that in order to deal with the case where more than one path metrics exhibit the smallest ones at a particular time point (t=5 in this case), the decoder 24 has been designed such as to select either one thereof. If the path metric of the state (10).sub.t=5 is selected as the smallest one, a decoded bit sequence S2' (FIG. 1) outputted from the maximum-likelihood decoder 24 becomes as follows. EQU S2'=(1 1 1 1 0 . . . ) (4)
It is understood that the decoded bit sequence S2' in expression (4) differs from the original bit sequence S2 (see expression (1)) which has been applied to the convolutional encoder 22 (FIG. 1).
Accordingly, the above mentioned prior art has encountered the problem in that the maximum-likelihood decoder 24 is not necessarily able to achieve a sufficient error correcting capability. This problem stems from the fact that the error correcting of the prior art is based merely on the redundant bits added at the convolutional encoder 22.